package Leetcode;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class sortList {
    /**
     * 对链表进行排序（使用归并排序）
     *
     * @param head 链表的头节点
     * @return 排序后的链表头节点
     */
    public ListNode sortList(ListNode head) {
        // 如果链表为空或只有一个节点，无需排序，直接返回
        if (head == null || head.next == null){
            return head;
        }

        // 使用快慢指针法找到链表的中间节点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;          // 慢指针每次移动一步
            fast = fast.next.next;     // 快指针每次移动两步
        }

        // 将链表分为两个部分
        ListNode second = slow.next;   // 第二个子链表的头节点
        slow.next = null;              // 断开第一个子链表的末尾
        ListNode first = head;         // 第一个子链表的头节点

        // 递归对两个子链表分别进行排序
        first = sortList(first);
        second = sortList(second);

        // 合并两个已排序的子链表，并返回合并后的链表头节点
        return mergeList(first, second);
    }

    /**
     * 合并两个有序链表为一个有序链表
     *
     * @param left  第一个有序链表的头节点
     * @param right 第二个有序链表的头节点
     * @return 合并后的有序链表的头节点
     */
    public ListNode mergeList(ListNode left, ListNode right) {
        // 创建一个虚拟头节点作为合并后链表的起点
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy; // 当前合并链表的尾节点

        // 遍历两个链表，将较小的节点添加到合并链表中
        while (left != null && right != null) {
            if (left.val < right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next; // 更新尾节点
        }

        // 如果仍有剩余节点，直接追加到合并链表的末尾
        if (left != null) {
            tail.next = left;
        } else {
            tail.next = right;
        }

        // 返回合并后的链表头节点
        return dummy.next;
    }
}
